package week_08;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 */
public class LongestPalindrome_logn_hash_5 {
    int p = (int) (1e9 + 7);
    int b = 131;
    int n;
    long[] preH;
    long[] p131;
    long[] subH;

    public String longestPalindrome(String s) {
        // 分奇偶数情况为中心向外扩
        if (s == null || s.length() < 1) {
            return "";
        }
        n = s.length();
        s = " " + s;
        char[] arr = s.toCharArray();
        preH = new long[n + 1];
        preH[0] = 0;
        p131 = new long[n + 1];
        p131[0] = 1;
        for (int i = 1; i <= n; i++) {
            preH[i] = (preH[i - 1] * b + (arr[i] - 'a' + 1)) % p;
            p131[i] = p131[i - 1] * b % p;
        }
        subH = new long[n + 2];
        subH[n + 1] = 0;
        for (int i = n; i > 0; i--) {
            subH[i] = (subH[i + 1] * b + (arr[i] - 'a' + 1)) % p;
        }
        int ansSize = 0;
        int idx = 0;
        //奇数情况
        //"babad"
        for (int center = 1; center <= n; center++) {
            int lenL = 0;
            int lenR = n;
            while (lenL < lenR) {
                int len = (lenL + lenR + 1) / 2;
                int l = center - len;
                int r = center + len;
                if (isPalindrome(l, r)) {
                    lenL = len;
                } else {
                    lenR = len - 1;
                }
            }
            // 停在 l-1 : r+1 越界位置
            if (2 * lenL + 1 > ansSize) {
                idx = center - lenL;
                ansSize = 2 * lenL + 1;
            }

        }

        // 偶数情况
        // "c*b*b*d"
        for (int center = 1; center < n; center++) {
            int lenL = 0;
            int lenR = n;
            while (lenL < lenR) {
                int len = (lenL + lenR + 1) / 2;
                int l = center - len + 1;
                int r = center + len;
                if (isPalindrome(l, r)) {
                    lenL = len;
                } else {
                    lenR = len - 1;
                }
            }
            if (2 * lenL > ansSize) {
                idx = center - lenL + 1;
                ansSize = 2 * lenL;
            }
        }
        return s.substring(idx, idx + ansSize);
    }

    public boolean isPalindrome(int l, int r) {
        if (l < 1 || r > n) return false;
        if (l > r) return true;
        return prefixHash(l, r) == subfixHash(l, r);
    }

    private long subfixHash(int l, int r) {

        return ((subH[l] - subH[r + 1] * p131[r - l + 1]) % p + p) % p;
    }

    private long prefixHash(int l, int r) {
        return ((preH[r] - preH[l - 1] * p131[r - l + 1]) % p + p) % p;
    }


}
